package arrays;

/**题目：矩阵置零
 * 给定一个m*n的二维数组，如果某个位置（i,j）的值为0,
 * 那么就把第i行和第j列的元素都置为零
 * @Author Gavin
 * @date 2022.01.02 22:42
 */
public class array_9 {
    /**
     * 第一种方法：通过for循环来处理
     */
    //Time:O(m*n) Space:O(m+n)
    public void solution_1(int[][] a){
        int m=a.length,n=a[0].length;
        boolean[] rows=new boolean[m];//存储某行是否应该置0
        boolean[] cols=new boolean[n];//存储某列是否应该置为0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(a[i][j]==0){
                    rows[i]=cols[j]=true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(rows[i]||cols[j]){
                    a[i][j]=0;
                }
            }
        }
    }
    /**
     * 第二种方法
     */
    //Time:O(m*n) Space:O(1)
    public void solution_2(int[][] a){
        int m=a.length,n=a[0].length;
        boolean row0=false,col0=false;

        for (int i = 0; i < m; i++) {
            if(a[i][0]==0)col0=true;
        }
        for (int i = 0; i < n; i++) {
            if(a[0][i]==0)row0=true;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j <n ; j++) {
                if(a[i][j]==0){
                    a[i][0]=a[0][j]=0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <n ; j++) {
                if(a[i][0]==0||a[0][j]==0){
                    a[i][j]=0;
                }
            }
        }
        if(row0){
            for (int i = 0; i < n; i++) {
                a[0][i]=0;
            }
        }
        if(col0){
            for (int i = 0; i < n; i++) {
                a[i][0]=0;
            }
        }
    }
}
